⟸ pàgina anterior ⟸
Exercici 5 (Tasca 4).
(context-free languages, depuration of grammars)

Depuració de gramàtiques

  1. Donada una gramàtica G, descriviu un algorisme per eliminar les \lambda-produccions (amb només una excepció possible) de G (sense canviar el llenguatge generat). Assegureu-vos que quan G és inambigua, l’algorisme descrit dona una gramàtica inambigua. Quin és el cost de l’algorisme?

  2. Donada una gramàtica G, descriviu un algorisme per eliminar les produccions unàries de G (sense canviar el llenguatge generat). Assegureu-vos que quan G és inambigua, l’algorisme descrit dona una gramàtica inambigua. Quin és el cost de l’algorisme?

  3. Donada una gramàtica G, descriviu un algorisme per eliminar els símbols inútils de G (sense canviar el llenguatge generat). Assegureu-vos que quan G és inambigua, l’algorisme descrit dona una gramàtica inambigua. Quin és el cost de l’algorisme?

  4. Apliqueu l’algorisme de depuració (eliminació de \lambda-produccions, produccions unàries, símbols no fecunds i inaccessibles) a les gramàtiques següents:

    1. \left\{\begin{array}{ccl} S &\to& SS \mid (S) \mid \lambda \end{array}\right.
    2. \left\{\begin{array}{ccl} S &\to& (S)S \mid \lambda \end{array}\right.
    3. \left\{\begin{array}{ccl} S &\to& AA \\ A &\to& AA\mid \lambda \end{array}\right.
    4. \left\{\begin{array}{ccl} S &\to& A \\ A &\to& B \\ B &\to& c \end{array}\right.
    5. \left\{\begin{array}{ccl} S &\to& AB \\ A &\to& a\mid \lambda \\ B &\to& b\mid \lambda \end{array}\right.
    6. \left\{\begin{array}{ccl} S &\to& AB \\ A &\to& aAb\mid \lambda \\ B &\to& bBc\mid \lambda \end{array}\right.
    7. \left\{\begin{array}{ccl} S &\to& BC \mid \lambda \\ A &\to& aA\mid \lambda \\ B &\to& bB \\ C &\to& c \end{array}\right.
    8. \left\{\begin{array}{ccl} S &\to& X\mid Y \lambda \\ X &\to& Xc\mid A \\ A &\to& aAb\mid \lambda \\ Y &\to& aY \mid B \\ B &\to& bBc \mid \lambda \end{array}\right.
    9. \left\{\begin{array}{ccl} S &\to& A\mid B \mid C \\ A &\to& SaSbS \mid \lambda \\ B &\to& SbSaS \mid \lambda \\ C &\to& Cc\mid \lambda \end{array}\right.